package 优先算法.前缀和.和可被k整除的子数组;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
 */
public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[] arr = {4,5,0,-2,-3,1};
        int rel = so.subarraysDivByK(arr, 5);
        System.out.println(rel);
    }
}
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0 % k,1);
        int sum = 0,rel = 0;//此处sum是前缀和余数
        for(int num : nums) {
            sum += num;
            int Y = (sum%k+k)%k;
            rel +=map.getOrDefault(Y,0);
            map.put(Y,map.getOrDefault(Y,0)+1);
        }
        return rel;
    }
}
